package com.bichengcao.googlecodejam.gcj2008beta;

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.Arrays;

public class ThePriceIsWrong {

	static int N;

	public static void main(String[] args) throws IOException {
		Input[] inputs = parseInput("src/com/bichengcao/googlecodejam/gcj2008beta/B-large-practice.in");
		Output[] outputs = process(inputs);
		writeOutput("src/com/bichengcao/googlecodejam/gcj2008beta/ThePriceIsWrong.out", outputs);
	}

	static class Input {

		int n;
		String[] products;
		int[] prices;
	}

	static class Output {

		String[] products;
	}
	
	private static Input[] parseInput(String filename) throws IOException {
		BufferedReader in = new BufferedReader(new FileReader(filename));
		N = Integer.parseInt(in.readLine());
		Input[] array = new Input[N];

		for (int i = 0; i < N; i++) {
			Input input = array[i] = new Input();
			String line = in.readLine();
			input.products = line.split(" ");
			line = in.readLine();
			String[] splits = line.split(" ");
			input.n = input.products.length;
			input.prices = new int[input.n];
			for (int j = 0; j < input.n; j++) {
				input.prices[j] = Integer.parseInt(splits[j]);
			}
		}

		in.close();
		return array;
	}

	private static Output[] process(Input[] inputs) {
		Output[] outputs = new Output[N];
		for (int i = 0; i < N; i++) {
			outputs[i] = process(inputs[i]);
		}
		return outputs;
	}

	private static Output process(Input input) {
		Output output = new Output();

		int lisLength = getLisLength(input.prices);
		output.products = new String[input.n - lisLength];
		
		String[] names = new String[input.n];
		String[] nameTemp = new String[input.n];
		for (int i = 0; i < input.n; i++) {
			nameTemp[i] = names[i] = input.products[i];
		}
		Arrays.sort(names);
		
		int outIndex = 0;
		int[] prices = Arrays.copyOf(input.prices, input.n);

		// Greedy test each product whether they are optional for the LIS
		for (int i = 0; i < names.length; i++) {
			for (int j = 0; j < prices.length; j++) {
				if (nameTemp[j] == names[i]) {
					int[] temp = new int[prices.length - 1];
					for (int k = 0; k < j; k++) {
						temp[k] = prices[k];
					}
					for (int k = j; k < prices.length - 1; k++) {
						temp[k] = prices[k + 1];
					}
					if (getLisLength(temp) == lisLength) {
						output.products[outIndex++] = names[i];
						prices = temp;
						for (int k = j; k < nameTemp.length - 1; k++) {
							nameTemp[k] = nameTemp[k + 1];
						}
					}
					break;
				}
			}
		}
		
		return output;
	}
	
	/**
	 * Get length of the longest increase subsequence of given array.
	 */
	private static int getLisLength(int[] array) {
		if (array.length == 0) return 0;
		int[] dp = new int[array.length];
		for (int i = 0; i < array.length; i++) {
			dp[i] = 1;
			for (int j = 0; j < i; j++) {
				if (array[i] > array[j] && dp[j] + 1 > dp[i]) {
					dp[i] = dp[j] + 1;
				}
			}
		}
		
		int lisLength = 0;
		for (int i = 0; i < array.length; i++) {
			if (dp[i] > lisLength) {
				lisLength = dp[i];
			}
		}
		return lisLength;
	}

	private static void writeOutput(String filename, Output[] outputs) throws IOException {
		PrintWriter out = new PrintWriter(new FileWriter(filename));
		for (int i = 0; i < N; i++) {
			out.print("Case #" + (i + 1) + ":");
			for (int j = 0; j < outputs[i].products.length; j++) {
				out.print(" " + outputs[i].products[j]);
			}
			out.println();
		}
		out.close();
	}

}
